import java.util.*;

/**
 * Created by zhourh on 2018/9/12.
 *
 * 给定一个保存员工信息的数据结构，它包含了员工唯一的id，重要度 和 直系下属的id。

 比如，员工1是员工2的领导，员工2是员工3的领导。他们相应的重要度为15, 10, 5。那么员工1的数据结构是[1, 15, [2]]，员工2的数据结构是[2, 10, [3]]，员工3的数据结构是[3, 5, []]。注意虽然员工3也是员工1的一个下属，但是由于并不是直系下属，因此没有体现在员工1的数据结构中。

 现在输入一个公司的所有员工信息，以及单个员工id，返回这个员工和他所有下属的重要度之和。

 示例 1:

 输入: [[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1
 输出: 11
 解释:
 员工1自身的重要度是5，他有两个直系下属2和3，而且2和3的重要度均为3。因此员工1的总重要度是 5 + 3 + 3 = 11。
 注意:

 一个员工最多有一个直系领导，但是可以有多个直系下属
 员工数量不超过2000。

 */
public class EmployeeImportance {

    public static void main(String[] args) {
        List<Employee> employees = new ArrayList<>();
        Employee employee1 = new Employee();
        employee1.id = 1;
        employee1.importance = 5;
        employee1.subordinates = new ArrayList<>();
        employee1.subordinates.add(2);
        employee1.subordinates.add(3);
        employees.add(employee1);

        Employee employee2 = new Employee();
        employee2.id = 2;
        employee2.importance = 3;
        employee2.subordinates = new ArrayList<>();
        employees.add(employee2);

        Employee employee3 = new Employee();
        employee3.id = 3;
        employee3.importance = 3;
        employee3.subordinates = new ArrayList<>();
        employees.add(employee3);

        System.out.println(new EmployeeImportance().getImportance2(employees, 1));


    }

    Map<Integer, Employee> employeeMap = new HashMap<>();

    public int getImportance2(List<Employee> employees, int id) {
        employeeMap.clear();

        for (Employee employee : employees) {
            employeeMap.put(employee.id, employee);
        }

        Employee employee = employeeMap.get(id);
        return getImportance(employee);
    }


    public int getImportance(Employee employee) {
        int important = employee.importance;
        if (employee.subordinates != null) {
            for (Integer subordinateId : employee.subordinates) {
                important += getImportance(employeeMap.get(subordinateId));
            }
        }

        return important;
    }


    public int getImportance(List<Employee> employees, int id) {
        if (employees == null || employees.isEmpty()) {
            return 0;
        }

        for (Employee employee : employees) {
            if (employee.id == id) {
                return employee.importance + getImportance(employees, employee.subordinates);
            }
        }

        return 0;
    }

    public int getImportance(List<Employee> employees, List<Integer> ids) {
        if (employees == null || employees.isEmpty() || ids == null || ids.isEmpty()) {
            return 0;
        }

        int importance = 0;
        List<Integer> idsCopy = new ArrayList<>();
        idsCopy.addAll(ids);

        for (Employee employee : employees) {
            if (idsCopy.contains(employee.id)) {
                importance += employee.importance + getImportance(employees, employee.subordinates);
                idsCopy.remove(new Integer(employee.id));
                if (idsCopy.isEmpty()) {
                    return importance;
                }
            }
        }
        return importance;
    }
}
